%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beamer Presentation
% LaTeX Template
% Version 1.0 (10/11/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND THEMES
%----------------------------------------------------------------------------------------

\documentclass{beamer}

\mode<presentation> {
\usetheme{Madrid} % very very good
}
\usepackage{pgfplots}

%\pgfplotsset{width=10cm,compat=1.9}
%\usepgfplotslibrary{external}
%
%\tikzexternalize
%



\usepackage{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables
\usepackage{pgf,pgfpages}
\usepackage{units}
\usepackage{listings}
\usepackage[utf8]{inputenc}

\usepackage[variablett]{lmodern}

\lstset{ %
  backgroundcolor=\color{white},   % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
%  basicstyle=\footnotesize,        % the size of the fonts that are used for the code
  language=C++,
%  basicstyle=\ttfamily,
  basicstyle=\ttfamily\scriptsize,
  keywordstyle=\color{blue}\ttfamily,
  stringstyle=\color{red}\ttfamily,
  commentstyle=\color{darkgreen}\ttfamily,
  breaklines=true,
  columns=flexible,
  literate={_}{\textsmallunderscore}1,
%  gobble=4,
%  xleftmargin=\leftmargini, 
%  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  captionpos=b,                    % sets the caption-position to bottom
  commentstyle=\color{green},      % comment style
  deletekeywords={...},            % if you want to delete keywords from the given language
  extendedchars=true,              
  frame=single,                    % adds a frame around the code
  keepspaces=true,                 
  keywordstyle=\color{blue},       % keyword style
  morekeywords={*,function, foreach, procedure, put, pop, remove,...},
  numbers=left,                    % where to put the line-numbers; possible values are (none, left, right)
  numbersep=5pt,                   % how far the line-numbers are from the code
  numberstyle=\tiny\color{black}, % the style that is used for the line-numbers
  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
  showstringspaces=false,          % underline spaces within strings only
  stepnumber=1,                    % the step between two line-numbers. If it's 1, each line will be numbered
%  stringstyle=\color{mauve},    	% string literal style
%  tabsize=4,                       % sets default tabsize to 2 spaces 
  title=\lstname,                   % show the filename of files included with \lstinputlisting; also try caption instead of title
  mathescape=true
}



%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\title[Short title]{Expérimentation sur GAC, MaxRPWC1, MaxRPWC3, rPIC, RPWC} % The short title appears at the bottom of every slide, the full title is only on the title page
\vspace{0.2cm}
\vspace{0.2cm}
\author{
Etudiant: KHONG Minh Thanh\\
Superviseurs: Yves Deville, Jean-Baptiste Mairy
\vspace{0.4cm}
}

\institute{
Institut de la Francophonie pour l'Informatique \\
\& beCool Constraints Group, ICTEAM/INGI, UCL
}
\begin{document}

\begin{frame}
\titlepage % Print the title page as the first slide
\end{frame}

\begin{frame}
\frametitle{Overview} % Table of contents slide, comment this block out to remove it
\tableofcontents % Throughout your presentation, if you choose to use \section{} and \subsection{} commands, these will automatically be printed on this slide as an overview of your presentation
\end{frame}

%----------------------------------------------------------------------------------------
%	PRESENTATION SLIDES
%----------------------------------------------------------------------------------------
%
%%------------------------------------------------
%\section{MaxRPWC1} 
%%------------------------------------------------
%\begin{frame}[fragile]
%\frametitle{Max-RPWC-1}
%Algorithme MaxRPWC1 \cite{domain:2008} 
%\begin{lstlisting}[caption=function Revise of Max-RPWC-1]
%function Revise($x_j, c_i,MaxRPWC$)
%   for each value $a \in D(x_j)$
%      PW $\leftarrow$ FALSE;
%      foreach valid $\tau (\in rel(c_i)) \geq_l lastGAC_{x_j,a,c_i}$ s.t. $\tau[x_j] = a$
%         PW $\leftarrow$ TRUE;
%         for each $c_m \neq c_i$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
%            if $\nexists$ valid $\tau' (\in rel(c_m))$ s.t. $\tau[vars(c_i) \cap vars(c_m)] = \tau' [vars(c_i) \cap vars(c_m)]$
%               PW $\leftarrow$ FALSE; break;
%         if PW = TRUE $lastGAC_{x_j,a,c_i} \leftarrow \tau$; break;
%      if PW = FALSE remove $a$ from $D(x_j)$;
%   return number of deleted values;
%\end{lstlisting}
%{\footnotesize
%Ligne 4-10 : pour chaque valide tuple $\tau \in rel(c_m), \tau[x_j]=a$, tester s'il peut étendre aux autres contraintes intersectées avec $c_i$. Si non, enlever $a$ de $D(x_j)$.\\
%Ligne 6-7 : pour chaque contrainte $c_m$, tester si $\tau$ a PW-support $\tau'$ dans $c_m$.\\
%Complexité : time : $O(e^2k^2d^p)$, space : $O(ekd)$, p : maximum nombre de variables dans deux contraintes intersectées
%
%}
%\end{frame}

%------------------------------------------------

%%------------------------------------------------
%\section{MaxRPWC}
%%------------------------------------------------
%%------------------------------------------------
%\section{Implémentation}
%%------------------------------------------------
%\begin{frame}
%\frametitle{Implémentation}
%Il y a deux classes principale à faire :
%\begin{itemize}
%\item MaxRPWC3 : 
%	\begin{itemize}
%	\item appeler la propagation 
%	\item trouver les intersections entre les contraintes
%	\end{itemize}
%\item ConstraintHardExtensionRPWC3 :
%	\begin{itemize}
%	\item contenir la méthode "runPropagator(Variable)" qui fait la fonction "Revise($x_j, c_i,MaxRPWC$)" pour réviser la consistance des variables de la contrainte
%	\end{itemize}
%\end{itemize}
%\end{frame}
%
%%------------------------------------------------
%
%\begin{frame}[fragile]
%\frametitle{Implémentation}
%Implémentation de la méthode "runPropagator(Variable)" :
%\begin{lstlisting}[caption=function runPropagator(Variable)]
%ConstraintHardExtensionRPWC3.runPropagator(Variable)
%   // $c_i$ is this constraint
%   for each variable $x_j \in c_i$ 
%      Revise($x_j, c_i,MaxRPWC$)
%   // update domain of all variable in $c_i$, return false if a domain of variable is empty   
%   return updateDomain()
%\end{lstlisting}
%\begin{itemize}
%\item Problème : 
%Ne pas implémenter $lastGAC_{x_j,a,c_i}$ à cause du changement des indexes des tuples, on doit donc chaque fois parcourir au début des tuples.
%\item Modification : 
%Enlever les tuples qui ne peut pas étendre aux autres tuples dans la fonction "Revise($x_j, c_i,MaxRPWC$)", il diminue les tuples à parcourir chaque fois
%\end{itemize}
%\end{frame}

%------------------------------------------------
\section{Expérimentation}
%------------------------------------------------
\begin{frame}
\frametitle{Expérimentation}
\begin{itemize}
\item L'expérimentation est lancé sur un PC de 4GB RAM, Core i5-2520M, Ubuntu. 
\item Le problèmes utilisés sont renault, random, random-fcd dans \cite{problem}. Le nombre de variable intersecté est 2-10. Algorithme de recherche : dom/ddeg.
\item Les consistances à tester sont GAC(algo STR2), MaxRPWC1, MaxRPWC3, rPIC, RPWC, PWC.
\item Les critères à considérer sont CPU time(s), et node.
\end{itemize}
\end{frame}
%------------------------------------------------

\begin{frame}
\frametitle{Expérimentation}
\small{
Le résultat (CPU time(s), node) :}
\begin{center}
\scalebox{0.75}{
    \begin{tabular}{ | p{2.0cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} |}
    \hline
    Problème  & GAC        	& RPWC 		& rPIC 		& Max-RPWC1 & Max-RPWC3 	& PWC+ GAC	\\ \hline
    renault-0 & 1.18, 166  	& 5.44, 114 & 23.56, \textbf{111} 	&  & 44.36, 111 & 5.90, \textbf{111}\\ \hline
    renault-1 & 5.07, 53775	& 603.18, 43244& 129.9, 550 	 	& & 25.64, 0 & 4.80, \textbf{0}\\ \hline
    renault-2 & 1.20, \textbf{111} & 2.98, \textbf{111} & $\geq$ 3600, - & $\geq$ 3600, - & 42.79, 111 & 5.45, \textbf{111}\\ \hline
    renault-3 & 3033.8, 20994648 &  & 78.13, 1215 &  & 37.80, 0 & 4.27, \textbf{0}\\ \hline
    renault-4 & 1.15, 114 	& 3.13, 112 & -  ,  -  & -  , - & 37.86, 112 & 5.80, \textbf{112}\\ \hline
    renault-5 & 330.8, 3231085& 882.03, 44491 & $\geq$ 5400  ,  - & $\geq$ 5400 ,  - & 84.05, 241 & 4.26, \textbf{0} \\ \hline
    renault-6 & 13.97, 115411 & & 56.58, 1307 &  & 553.0, 52831  & 17.97, 52831\\ \hline
    renault-7 & 1.38, 134 	& 6.84, 120 & 12.07, 116&  & 39.22, 113 & 5.17, \textbf{112}\\ \hline
    renault-8 & 11.27, 180955 & 1637.3, 11363 & 73.39, 1094 &  & 271.08, 12336 & 4.25, \textbf{0}\\ \hline
    
    rand-3-20-20-60-632-fcd-2\_ext & 56.93, 69199 &  598.93, 36131 & 619.0, 43740 &  & 266.8, 43740 & 92.10, 18248 \\ \hline
    \end{tabular}
}
\end{center}
\end{frame}


%%------------------------------------------------
%
%\begin{frame}
%\frametitle{Expérimentation}
%\small{
%Le résultat (CPU time(s), node) :}
%\begin{center}
%\scalebox{0.75}{
%    \begin{tabular}{ | p{2.0cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} |}
%    \hline
%    Problème  & GAC        & RPWC 		& rPIC 		& Max-RPWC1 	& Max-RPWC3 	& PWC+ GAC	\\ \hline
%    rand-3-20-20-60-632-4\_ext & \textbf{12.02, 31453} & 689.7, 76152 & 889.6, 66270 & 767.4, 66270 & 372.3, 66270 & 188.9, 147687 \\ \hline
%    rand-3-20-20-60-632-8\_ext & \textbf{16.57}, 43795  & 424.2, 62650 & 661.6, 58323 & 542.78, 58323 & 287.6, 58323 & 38.1, \textbf{20825}\\ \hline
%    rand-3-20-20-60-632-9\_ext & \textbf{39.62}, 71345 & 242.7, \textbf{24975} & 1045.7, 77462 & 947.5, 77462 & 478.7, 77462 & 106.7, 47391\\ \hline
%    rand-3-20-20-60-632-fcd-15\_ext & \textbf{29.26}, 43555 & 349.12, 48113 & 449.5, 37727 & 394.83, 37727 & 200.4, 37727 & 42.3, \textbf{16545}\\ \hline
%    rand-3-20-20-60-632-fcd-2\_ext & 39.49, 49866 & 276.3, 36338 & 619.0, 43740 & 522.0, 43740 & 266.8, 43740 & \textbf{9.45, 3636} \\ \hline
%    rand-3-20-20-60-632-fcd-8\_ext & \textbf{38.30}, 83173 & 333.5, \textbf{54973} & 1420.4, 105426 & 982.4, 105426& 501.4, 105426 & 122.0, 95600\\ \hline
%    \end{tabular}
%}
%\end{center}
%\end{frame}

%------------------------------------------------
%%
%\begin{frame}
%\frametitle{Expérimentation}
%\pgfplotsset{every axis/.append style={
%                    legend style={font=\tiny,line width=.5pt,mark size=.6pt},
%                    }}
%
%\begin{center}
%\scalebox{0.9}{
%	\begin{tikzpicture} 
%	\begin{semilogyaxis}[ xlabel={renault instance}, ylabel={CPU time(s)} ] 
%	\addplot coordinates { 
%	(0, 0.53 ) (1, 0.70) (2, 0.69) (3, 0.88) (4, 0.80) (5, 1.00) (6, 1.08) (7, 0.93) (8, 0.82)}; 
%	\addplot coordinates{ 
%	(0, 3.06) (1, 33.44) (2, 1.65) (3, 34.37) (4, 1.64) (5, 42.99) (6, 25.01) (7, 2.50) (8, 25.81)}; 
%	\addplot coordinates{ 
%	(0, 12.62) (1, 71.16) (2, 10.34) (3, 78.13) (4, 7.96) (5, 92.45) (6, 56.58) (7, 12.07) (8, 73.39)}; 
%	\addplot coordinates{ 
%	(0, 14.16 ) (1, 37.83) (2, 12.84) (3, 79.74) (4, 11.71) (5, 64.31) (6, 43.92) (7, 12.37) (8, 56.34)}; 
%	\addplot coordinates{ 
%	(0, 17.77 ) (1, 31.35) (2, 14.33) (3, 36.77) (4, 16.82) (5, 46.22) (6, 35.07) (7, 12.62) (8, 36.43)}; 
%	\addplot coordinates{ 
%	(0, 3.40 ) (1, 1.95) (2, 3.21) (3, 2.45) (4, 2.29) (5, 1.81) (6, 5.02) (7,2.63 ) (8, 1.99)}; 
%	\legend{$GAC$,$RPWC$,$rPIC$,$MaxRPWC1$,$MaxRPWC3$,$PWC+GAC$} 
%	\end{semilogyaxis} 
%	\end{tikzpicture}
%}
%\end{center}
%\end{frame}

%------------------------------------------------
%
%\begin{frame}
%\frametitle{Expérimentation}
%
%\end{frame}
%
%%------------------------------------------------
%
%%------------------------------------------------
%\section{Perspective}
%%------------------------------------------------
%\begin{frame}
%\frametitle{Perspective}
%
%\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{References}
\footnotesize{
\begin{thebibliography}{99} % Beamer does not support BibTeX so references must be inserted manually as below
\bibitem{domain:2008} Bessiere, Christian, Kostas Stergiou, and Toby Walsh. "Domain filtering consistencies for non-binary constraints." Artificial Intelligence 172.6 (2008): 800-822.
\bibitem{problem} http://www.cril.univ-artois.fr/lecoutre/benchmarks.html
\end{thebibliography}
}
\end{frame}

%%------------------------------------------------
%
%\begin{frame}
%\Huge{\centerline{The End}}
%\end{frame}

%----------------------------------------------------------------------------------------

\end{document} 